1659C - Line Empire - CodeForces Solution


brute force dp greedy implementation math

Please click on ads to support us..

Python Code:

def inp(): return int(input())
def strng(): return input().strip()
def jn(x, l): return x.join(map(str, l))
def strl(): return list(input().strip())
def mul(): return map(int, input().strip().split())
def mulf(): return map(float, input().strip().split())
def seq(): return list(map(int, input().strip().split()))
def ceil(x): return int(x) if(x == int(x)) else int(x)+1
def ceildiv(x, d): return x//d if(x % d == 0) else x//d+1

for i in range(inp()):
    n,a,b = mul()
    lst = seq()
    l =[]
    l.append(sum(lst)*b)
    m = []
    s1 =sum(lst)
    a1=0
    for i in range(0,n):
        m.append(s1-lst[i]-a1)
        a1+=lst[i]
    for i in range(0,n):
        c1 = (lst[i]-0)*b+((i+1-n)*lst[i]+m[i])*b
        c2=a*(lst[i]-0)
        if l[0]>(c1+c2):
            l[0]=c1+c2
    print(l[0])

C++ Code:

#include<bits/stdc++.h>
#define ll long long
#define rep(i,a,b) for(int i=a;i<b;i++)
#define rrep(i,a,b) for(int i=a;i>=b;i--)
#define repin rep(i,0,n)
#define di(a) ll a;cin>>a;
#define sin string s;cin>>s;
#define dia di(a)
#define dib di(b)
#define dic di(c)
#define dix di(x)
#define diy di(y)
#define diz di(z)
#define dik di(k)
#define din di(n)
#define dim di(m)
#define diq di(q)
#define endl '\n'
#define precise(i) cout<<fixed<<setprecision(i)
#define V vector<ll>
#define pb push_back
#define M map<ll,ll>
#define take(a,n) for(int j=0;j<n;j++) cin>>a[j];
#define give(a,n) for(int j=0;j<n;j++) cout<<a[j]<<' ';
#define vpii vector<pair<ll,ll>>
#define all(x) x.begin(),x.end()
#define back(x) x.rbegin(),x.rend()
#define MOD 1000000007
#define db long double
#define fastio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;
// const int N =998244353;


int main(){
    fastio;
    

    ll T=1;
    cin>>T;
    // int ogt=0;
    while(T--){
        // ogt++;

        din;
        dia;
        dib;
        V v(n);
        take(v,n);
        ll ans = b*v[0];
        ll curr =0;

        if(a<b*(n-1)) {
            ans += a*v[0];
            curr=v[0];
        }
        for (int i = 1; i < n; ++i)
        {
            if(a<b*(n-1-i)){
                ans += (b+a)*(v[i]-curr);
                curr=v[i];
            }
            else {
                ans += b*(v[i]-curr);
            }
        }

        cout<<ans<<endl;
        
        
        


    }
    return 0;
}   


Comments

Submit
0 Comments
More Questions

1176A - Divide it
1527A - And Then There Were K
1618E - Singers' Tour
1560B - Who's Opposite
182B - Vasya's Calendar
934A - A Compatible Pair
1618F - Reverse
1684C - Column Swapping
57C - Array
1713D - Tournament Countdown
33A - What is for dinner
810A - Straight A
1433C - Dominant Piranha
633A - Ebony and Ivory
1196A - Three Piles of Candies
299A - Ksusha and Array
448B - Suffix Structures
1092B - Teams Forming
1166C - A Tale of Two Lands
544B - Sea and Islands
152B - Steps
1174D - Ehab and the Expected XOR Problem
1511A - Review Site
1316A - Grade Allocation
838A - Binary Blocks
1515D - Phoenix and Socks
1624D - Palindromes Coloring
1552F - Telepanting
1692G - 2Sort
1191A - Tokitsukaze and Enhancement